class Solution {
public:
    int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit) {
        const int MOD=1e9+7;
        int len=group.size();
        vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(n+1,vector<int>(m+1)));
        for(int j=0;j<=n;j++)dp[0][j][0]=1;
        for(int i=1;i<=len;i++)
            for(int j=0;j<=n;j++)
                for(int k=0;k<=m;k++)
                {
                    dp[i][j][k]=dp[i-1][j][k];
                    if(j>=group[i-1])
                        dp[i][j][k]+=dp[i-1][j-group[i-1]][max(0,k-profit[i-1])];
                    dp[i][j][k]%=MOD;
                }
        return dp[len][n][m];
    }
};
